package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/13.
 */
public class AddList {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 你有两个用链表代表的整数，其中每个节点包含一个数字。
     * 数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。
     * 写出一个函数将两个整数相加，用链表形式返回和。
     * 给出两个链表 3->1->5->null 和 5->9->2->null，返回 8->0->8->null
     * */
    public ListNode addList1(ListNode node1, ListNode node2) {
        ListNode listNode1 = node1;
        ListNode listNode2 = node2;
        ListNode p = new ListNode(-1);
        int flag = 0;
        while (listNode1 != null || listNode2 != null) {
            int temp = flag;
            if (listNode1 != null) {
                temp += listNode1.val;
                listNode1 = listNode1.next;
            }
            if (listNode2 != null) {
                temp += listNode2.val;
                listNode2 = listNode2.next;
            }
            if (temp > 9) {
                temp -= 10;
                flag = 1;
            } else {
                flag = 0;
            }
            p.next = new ListNode(temp);
            p = p.next;
        }
        if (flag == 1) {
            p.next = new ListNode(1);
        }
        return p.next;
    }

    /**
     * 假定用一个链表表示两个数，其中每个节点仅包含一个数字。
     * 假设这两个数的数字顺序排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。
     * 给出 6->1->7 + 2->9->5。即，617 + 295。
     * 返回 9->1->2。即，912 。
     * 思路：翻转之后转化成上面的问题，然后计算结果，然后在翻转一次就行了
     * */

    public ListNode addList2(ListNode listNode1, ListNode listNode2){

        ListNode l11 = reverse(listNode1);
        ListNode l22 = reverse(listNode2);
        ListNode p1 = l11;
        ListNode p2 = l22;
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        int flag = 0;
        while (p1 != null || p2 != null){
            int temp = flag;
            if (p1 != null){
                temp += p1.val;
                p1 = p1.next;
            }
            if (p2 != null){
                temp += p2.val;
                p2 = p2.next;
            }
            if (temp > 9){
                temp -= 10;
                flag = 1;
            }else {
                flag = 0;
            }

            ListNode node = new ListNode(temp);
            p.next = node;
            p = p.next;
        }
        if (flag == 1){
            ListNode node = new ListNode(1);
            p.next = node;
        }
        return reverse(dummy.next);
    }

    public ListNode reverse(ListNode head){
        ListNode newHead = null;
        while (head != null){
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
}
